package Year2013;

/**
 * 标题:振兴中华
 * 小明参加了学校的趣味运动会，其中的一个项目是:跳格子。
 * 地上画看一些格子，每个格子里写一个字，如下所示: (也可参 见p1. jpg)
 *      从我做起振
 *      我做起振兴
 *      做起振兴中
 *      起振兴中华
 * 比赛时，先站在左上角的写着“从”字的格子里，可以横向或纵向跳到相邻的格子里，但不能跳到对角的格子或其它位置。- 直要跳到“华”字结束。
 * 要求跳过的路线刚好构成”从我做起振兴中华”这句话。
 * 请你帮助小明算算他一共有多少种可能的跳跃路线呢?
 * 答案是一个整数，请通过浏览器直接提交该数字。
 * 注意:不要提交解答过程，或其它辅助说明类的内容。
 */
public class C组_振兴中华 {
    // 从我做起振兴中华 == 0,1,2,3,4,5,6,7
    static int[][] squre = {    {0,1,2,3,4},
                                {1,2,3,4,5},
                                {2,3,4,5,6},
                                {3,4,5,6,7}};
    static int[][] direction = {{0,1},
            {1,0},
            {-1,0},
            {0,-1}}; //右下左上
    static int top = 1;
    static int m=4,n=5,count=0; //m行n列
    public static void main(String[] args) {
        recurision(0,0);
        System.out.println("法1：count："+count);
        System.out.println("法2："+recurision01(0,0));
    }

    /**
     * 适用与复杂题目
     * @param x
     * @param y
     */
    static void recurision(int x,int y){  // x 行 ， y 列
        int newX,newY;
        // 结束条件
        if(x == m-1 && y == n-1){
            count++;
            return;
        }
        // 深度优先搜索
        for (int i = 0; i < 4; i++) { // 遍历四个方向
            newX = x+direction[i][0];
            newY = y+direction[i][1];
            if( 0<=newX && newX< m && 0<=newY && newY<n){ // 判断：边界，是否为1（强）
                if((squre[newX][newY] == top)){
                    top++;
                    recurision(newX,newY); // 递归
                    top--;
                }
            }
        }
    }

    /**
     * 适用于简单题目
     * @param x
     * @param y
     * @return
     */
    static int recurision01(int x,int y){  // x 行 ， y 列
       if(x == 3 || y == 4)
           return 1;
       return recurision01(x+1,y) + recurision01(x,y+1);
    }
}
